import Foundation

public class TreeNode {
    public var val: Int
    public var left: TreeNode?
    public var right: TreeNode?
    public init(_ val: Int) {
        self.val = val
        self.left = nil
        self.right = nil
    }
}

/*
 剑指 Offer 07. 重建二叉树
 输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

  

 例如，给出

 前序遍历 preorder = [3,9,20,15,7]
 中序遍历 inorder = [9,3,15,20,7]
 返回如下的二叉树：

     3
    / \
   9  20
     /  \
    15   7
 **/

// 前序，特点：第一个是根节点
// 中序，特点：根节点分割了左子树、右子树

// 根据中序分割出来的左右子树，节点个数，去前序中查找

func buildTree(_ preorder: [Int], _ inorder: [Int]) -> TreeNode? {
    
    guard preorder.count > 0 else {
        return nil
    }
    return createTree(preorder, 0, preorder.count-1, inorder, 0, inorder.count-1)
}

func createTree(_ preorder: [Int], _ preStart: Int, _ preEnd: Int, _ inorder: [Int], _ inStart: Int, _ inEnd: Int) -> TreeNode? {
    if preStart > preEnd {
        return nil
    }
    
    let target = preorder[preStart]
    
    let node = TreeNode(target)
    let inIndex = getInorderIndex(inorder, inStart, inEnd, target)
    let inLeftCount = inIndex - inStart
    let inRightCount = inEnd - inIndex
    
    if inLeftCount > 0 {
        node.left = createTree(preorder, preStart, preStart+inLeftCount, inorder, inStart, inIndex-1)
    } else {
        node.left = nil
    }
    
    if inRightCount > 0 {
        node.right = createTree(preorder, preStart+inLeftCount+1, preEnd, inorder, inIndex+1, inEnd)
    } else {
        node.right = nil
    }
    
    return node
}


func getInorderIndex(_ inorder: [Int], _ start: Int, _ end: Int, _ value: Int) -> Int {
    for index in start...end {
        if inorder[index] == value {
            return index
        }
    }
    return 0
}
